class Queue {
    #list = [];
    #size; // 最大长度

    constructor(size){
        this.#size = size;
    }

    //向队列中添加数据，队列的第一个位置插入
    push(data) {
        if (data == null) {
            return false;
        }
        //如果传递了size参数就设置了队列的大小
        if (this.#size) {
            if (this.#list.length == this.#size) {
                this.pop();
            }
        }
        this.#list.unshift(data);
        return true;
    }

    enQueue(data){
        this.push(data);
    }

    deQueue(){
        this.pop();
    }

    //从队列中取出数据，最后一个元素
    pop() {
        return this.#list.pop();
    }

    //返回队列的大小
    size() {
        return this.#list.length;
    }

    //返回队列的内容
    queue() {
        return this.#list;
    }
}




/* 
..!.!..!....
.S.......!..
.......!....
....!.!.!!..
.!...!..!T!.
....!.!.....
*/

/* 表示最短路径 */

class Node {
    #isAccess;
    #parent;
    #value;
    #x;
    #y;
    
    get isAccess(){
        return this.#isAccess;
    }
    set isAccess(isAccess){
        this.#isAccess = isAccess;
    }
    get parent(){
        return this.#parent;
    }
    set parent(parent){
        this.#parent = parent;
    }
    get value(){
        return this.#value;
    }
    set value(value){
        this.#value = value;
    }
    get x(){
        return this.#x;
    }
    set x(x){
        this.#x = x;
    }
    get y(){
        return this.#y;
    }
    set y(y){
        this.#y = y;
    }

    static string2map(map){
        let result = [];
        let currentX = 0, currentY = 0;
        let array = [];
        for(let char of map){
            if(char === '\n'){
                result.push(array);
                currentY++;
                currentX = 0;
                array = [];
                continue;
            }
            let node = new Node();
            node.x = currentX;
            node.y = currentY;
            node.value = char;
            array.push(node);
            currentX++;
        }
        return result;
    }
}


class PathUtil{
    
    /**
        @param sourse 初始地址
        @param target 目的地址
        @param path   路径
        深度优先算法 
    */
    DFS_Search(sourse, target, path){
        
    }


    /** 
        @param sourse 初始地址
        @param target 目的地址
        @param path   路径
        广度优先算法 
    */
    static BFS_Search(map, mapWidth, mapHeight, sourse, target, path = []){
        for(let i = 0; i < mapHeight; i++){
            for(let j = 0; j < mapWidth; j++){
                // 访问了就不访问了；访问过就是说明有最短路径
                let currentNode = map[i][j];
                currentNode.x = i;
                currentNode.y = j;
                if(!currentNode.isAccess){
                    PathUtil.BFS(map, mapWidth, mapHeight, currentNode, sourse, target, path);
                    if(path.length){
                       return path; 
                    }
                }
            }
        }
        return path;
    }


    static BFS(map, mapWidth, mapHeight, currentNode, sourseNode, targetNode, path){
        let queue = new Queue();
        queue.push(currentNode);
        while(queue.size()){
            let head = queue.pop();
            // 获取当前节点的相邻节点
            let neighborList = PathUtil.neighbor(map, head, mapWidth, mapHeight);
            for(let i = 0; i < neighborList.length; i++){
                // 未被访问且能访问
                if(!neighborList[i].isAccess && neighborList[i].value !== "!"){
                    queue.push(neighborList[i]);
                    neighborList[i].parent = head;
                    neighborList[i].isAccess = true;
                    console.log(neighborList[i].value, targetNode.value);
                    if (neighborList[i].value === targetNode.value){
                        path.push(targetNode);
                        while(neighborList[i].value !== sourseNode.value){
                            neighborList[i] = neighborList[i].parent;
                            path.push(neighborList[i]);
                        }
                        return;
                    }
                }
            }
        }
    }

    static neighbor(map, currentNode, mapWidth, mapHeight){
        // 上下左右
        let currentXList = [-1, 0, 1, 0], currentYList = [0, -1, 0, 1], neighborList = [];
        for(let i = 0; i < 4; i++){
            let currentX = currentXList[i] + currentNode.x;
            let currentY = currentYList[i] + currentNode.y;
            if(currentX < 0 || currentX >= mapWidth || currentY < 0 || currentY >= mapHeight){
                continue;
            }
            let node = map[currentY][currentX];
            node.x = currentX;
            node.y = currentY;
            neighborList.push(node);
        }
        return neighborList;
    }
}

let map = Node.string2map("\
..!.!..!....\n\
.S.......!..\n\
............\n\
....!.!.!!..\n\
.!...!..!T!.\n\
....!.!.....\n");

let sourse = new Node();
sourse.value = "S";
let target = new Node();
target.value = "T";

let path = PathUtil.BFS_Search(map, 12, 6, sourse, target);

console.log(path);





